package com.klun.likou;

import com.klun.likou.base.ListNode;

public class Solution25 {
	/**
	 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
	 * k 是一个正整数，它的值小于或等于链表的长度。
	 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode head1 = ListNode.genAscNode(100000);
		ListNode head2 = ListNode.genAscNode(100000);
		long l = System.currentTimeMillis();
		ListNode result1 = reverseKGroup(head1, 50);
		long ll = System.currentTimeMillis();
		ListNode result2 = reverseKGroupG(head2, 50);
		long lll = System.currentTimeMillis();
		System.out.println("result1:" + (ll - l));
		System.out.println("result2:" + (lll - ll));
	}

	public static ListNode reverseKGroup(ListNode head, int k) {
		if (head == null) return null;
		if (k == 1) return head;
		ListNode kNode = head; // 找到第k个node
		int count = 1;
		do {
			count++;
			kNode = kNode.next;
			if (count == k || null == kNode) break;
		} while (true);
		return reverseKGroup(head, kNode, k);
	}

	public static ListNode reverseKGroup(ListNode head, ListNode kNode, int k) {
		if (head == null) return head;
		if (kNode == null) return head;
		ListNode start = head; // 记录翻转后头部
		ListNode end = head; // 记录翻转后最后一个
		for (int i = 0; i < k - 1; i++) {
			if (null != kNode) {
				kNode = kNode.next;
			}
			ListNode next = end.next;
			if (next == null) {
				return start;
			}
			ListNode nNext = next.next;
			// 交换位置
			next.next = start;
			end.next = nNext;
			start = next;
			if (i == k - 2 || nNext == null) {
				// nNext 成为下一个的开始
				ListNode listNode = reverseKGroup(nNext, null == kNode ? null : kNode.next, k);
				head.next = listNode;
				return start;// 末尾一个成为头部
			}
		}
		return head;
	}

	/**
	 * 之前最快的
	 *
	 * @param head
	 * @param k
	 * @return
	 */
	public static ListNode reverseKGroupG(ListNode head, int k) {
		if (head == null)
			return head;

		int count = k - 1;
		ListNode startNode = head, stopNode = head;     //待反转结点的第一个和最后一个
		while (stopNode.next != null && count != 0) {
			stopNode = stopNode.next;
			count--;
		}
		if (count != 0)        //不到K个结点直接返回
			return head;
		ListNode next = stopNode.next;      //保存最后一个待反转结点的下一个结点
		stopNode = reverse(startNode, stopNode);    //原来的最后一个结点变为头结点
		startNode.next = reverseKGroup(next, k);    //原来的第一个结点变为尾结点，递归处理剩余链表

		return stopNode;
	}

	static ListNode reverse(ListNode startNode, ListNode stopNode) {    //链表反转
		ListNode pre = null, cur = startNode, stop = stopNode.next;
		while (cur != stop) {
			ListNode temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}

		return pre;
	}
}